package res.graph;

import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public abstract class ReadableGraph implements Graph {
	
	protected Collection<Edge> edges;
	protected final Vertex[] vertices;
	protected final int numvertices;

	public ReadableGraph(int numvertices) {
		this.numvertices = numvertices;
		this.vertices = new Vertex[numvertices];
		
		for(int i = 0; i < numvertices; i++)
			vertices[i] = new Vertex(this, i);
	}
	
	public abstract Vertex getVertex(int n);
	public abstract Edge addEdge(int u, int v);
	public abstract Edge addEdge(int u, int v, double weight);
	
	public final int getNumVertices() {
		return numvertices;
	}

	@Override
	public Iterable<Edge> getEdges() {
		return edges;
	}

	/**
	 * @return um iterador que devolve os vértices na ordem de um percurso em largura a partir do 1&ordm; vértice do grafo.
	 */
	@Override
	public Iterator<Vertex> iterator() {
		return new BreadthFirstIterator();
	}

	@Override
	public final Iterator<Vertex> bradthFirstIterator() {
		return new BreadthFirstIterator();
	}

	@Override
	public final Iterator<Vertex> depthFirstIterator() {
		return new DepthFirstIterator();
	}
	
	/**
	 * @author araruna
	 *
	 */
	protected final class BreadthFirstIterator implements Iterator<Vertex> {
		Queue<Vertex> traversal = new LinkedList<Vertex>();
		private Queue<Vertex> marked = new LinkedList<Vertex>();
		private HashSet<Vertex> markedOrVisited = new HashSet<Vertex>(vertices.length);
		
		public BreadthFirstIterator() {
			breadthFirstSearch(vertices[0]);
		}
		
		public BreadthFirstIterator(Vertex v) {
			if(v.getGraph() != ReadableGraph.this)
				throw new IllegalStateException("The vertex must belong to the same graph of the iterator.");
			
			breadthFirstSearch(v);
		}
		
		private void breadthFirstSearch(Vertex s) {
			marked.add(s);
			markedOrVisited.add(s);
			
			while(!marked.isEmpty()) {
				Vertex v = marked.remove();
				traversal.add(v);
				
				for(Vertex target : v.getOutNeighbourhood()) { 
					if(!markedOrVisited.contains(target)) {
						marked.add(target);
						markedOrVisited.add(target);
					}
				}
			}
		}

		/** (non-Javadoc)
		 * @see java.util.Iterator#hasNext()
		 */
		@Override
		public boolean hasNext() {
			return (!traversal.isEmpty());
		}

		/** (non-Javadoc)
		 * @see java.util.Iterator#next()
		 */
		@Override
		public Vertex next() {
			return traversal.remove();
		}

		/** (non-Javadoc)
		 * @see java.util.Iterator#remove()
		 */
		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}

	}
	
	/**
	 * @author araruna
	 *
	 */
	protected final class DepthFirstIterator implements Iterator<Vertex> {
		private Queue<Vertex> traversal = new LinkedList<Vertex>();
		private Deque<Vertex> marked = new LinkedList<Vertex>();
		
		private HashSet<Vertex> markedOrVisited = new HashSet<Vertex>(vertices.length);
		
		public DepthFirstIterator() {
			depthFirstSearch(vertices[0]);
		}
		
		public DepthFirstIterator(Vertex v) {
			if(v.getGraph() != ReadableGraph.this)
				throw new IllegalStateException("The vertex must belong to the same graph of the iterator.");
			
			depthFirstSearch(v);
		}
		
		// TODO Verificar se está correto
		private void depthFirstSearch(Vertex s) {
			marked.add(s);
			markedOrVisited.add(s);
			
			while(!marked.isEmpty()) {
				Vertex v = marked.pop();
				traversal.add(v);
				
				for(Vertex target : v.getOutNeighbourhood()) {
					if(!markedOrVisited.contains(target)) {
						marked.push(target);
						markedOrVisited.add(target);
					}
				}
			}
		}

		/** (non-Javadoc)
		 * @see java.util.Iterator#hasNext()
		 */
		@Override
		public boolean hasNext() {
			return (!traversal.isEmpty());
		}

		/** (non-Javadoc)
		 * @see java.util.Iterator#next()
		 */
		@Override
		public Vertex next() {
			return traversal.remove();
		}

		/** (non-Javadoc)
		 * @see java.util.Iterator#remove()
		 */
		@Override
		public void remove() {
			throw new UnsupportedOperationException();
		}

	}
}
